package com.yhk.array;

/**
 * @version 1.0
 * @Author moresuo
 * @Date 2024/10/9 22:05
 * @注释 环形数组
 */
public class CycleArray<T> {
    //存储数组
    private T[] data;
    //头指针
    private int start;
    //尾指针
    private int end;
    //元素个数
    private int count;
    //数组的容量
    private int size;

    public CycleArray() {
        this(1);
    }

    public CycleArray(int size) {
        this.size=size;
        this.data = (T[]) new Object[size];
        //初始化头尾指针
        this.start=0;
        this.end=0;
        //初始化元素个数
        this.count=0;
    }

    /**
     * 添加元素到头部
     * @param val 元素
     */
    public void addFirst(T val) {
        //判断数组容量是否已满
        if (count == size) {
            //扩容
            resize(size * 2);
        }
        //获取要插入位置的下标,头指针左边的位置
        int index=(start-1+size)%size;
        data[index]=val;
        //元素个数加一
        count++;
        //改变头指针
        start=index;
    }

    /**
     * 删除头部元素
     */
    public void removeFirst() {
        //判断数组是否为空
        if (isEmpty()) {
            throw new IllegalStateException("Array is Empty");
        }
        //因为start是闭区间，所以先赋值，在左移
        data[start]=null;
        start=(start+1)%size;
        //元素个数减一
        count--;
        //自动扩缩容
        if (count > 0 && count == size / 4) {
            resize(size / 2);
        }
    }

    /**
     * 添加元素到末尾
     * @param val 元素
     */
    public void addLast(T val) {
        //判断数组是否已满
        if (count == size) {
            resize(size * 2);
        }
        data[end]=val;
        end=(end+1)%size;
        //元素个数加一
        count++;
    }

    /**
     * 删除元素尾部元素
     */
    public void removeLast() {
        //判断数组是否为空
        if (isEmpty()) {
            throw new IllegalStateException("Array is Empty");
        }
        //因为end是开区间，所以先左移再赋值
        end=(end-1+size)%size;
        data[end]=null;
        //元素个数减一
        count--;
        //缩容
        if (count > 0 && count == size / 4) {
            resize(size / 2);
        }
    }

    /**
     * 获取头部元素
     * @return
     */
    public T getFirst() {
        //判断是否为空
        if (isEmpty()) {
            throw new IllegalStateException("Array is Empty");
        }
        return data[start];
    }

    /**
     * 获取尾部元素
     * @return
     */
    public T getLast() {
        //判断是否为空
        if (isEmpty()) {
            throw new IllegalStateException("Array is Empty");
        }
        return data[(end - 1 + size) % size];
    }


    /**
     * 判断数组是否为空
     * @return
     */
    private boolean isEmpty() {
        return count==0;
    }

    /**
     * 自动扩缩容
     * @param newSize 新容量
     */
    private void resize(int newSize) {
        //设置一个新数组
        T[] newData = (T[]) new Object[newSize];
        //将旧数组元素复制到新数组当中
        for (int i = 0; i < count; i++) {
            int index=(start+i)%size;
            newData[i]=data[index];
        }
        data=newData;
        //改变容量
        size=newSize;
        //重置头尾指针
        start=0;
        end=count;
    }
}
